class LinkedQueueWithSentinel:
    """
    FIFO queue implementation using a singly sentinel linked list.
    """
    class _Node:
        """Singly linked node"""
        __slots__ = '_element', '_next'

        def __init__(self, element, next):
            self._element = element
            self._next = next

    def __init__(self):
        self._header: LinkedQueueWithSentinel._Node = self._Node(None, None)
        self._size = 0
        self.tail: LinkedQueueWithSentinel._Node = None

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def __str__(self):
        data = []
        if self._size > 0:
            walk = self._header._next
            while walk:
                data.append(walk._element)
                walk = walk._next
        return str(data)

    def first(self):
        """Return the element at the front of queue"""
        if self.is_empty():
            raise Exception("queue is empty")
        return self._header._next._element

    def enqueue(self, e):
        """
        Add an element to the tail of the queue
        :param value:
        :return:
        """
        new_node = self._Node(e, None)
        if self.is_empty():
            self._header._next = new_node
        else:
            self.tail._next = new_node

        self.tail = new_node
        self._size += 1

    def dequeue(self):
        """
        Remove and return the first element of the queue.
        :return:
        """
        if self.is_empty():
            raise Exception("queue is empty")
        delete_node = self._header._next
        self._header._next = delete_node._next
        value = delete_node._element
        self._size -= 1
        delete_node = None
        if self.is_empty():
            self.tail = None
        return value


